NAND (Sheffer Stroke - ↑) と NOR (Peirce’s Arrow - ↓)

NANDとNORは、それぞれ一種類の論理結合子だけで否定・論理積・論理和を表現できる完全結合子である。表現力の最小性を考える例であり、回路やSATのエンコーディングにも現れる。

仕組みと確認

NAND(A,A)で否定を作り、否定とNANDの組合せで他の結合子を構成する。NORでも同様の構成を真理値表で確認し、回路のゲート数・遅延・故障を別に評価する。

限界と注意点

表現できることと、実装が小さい・速い・安全であることは別である。論理の二値性、信号のタイミング、短絡評価、副作用の有無を明示する。